Матч 324, Упаковка продуктов (ProductBundling)

Дивизион 2, Уровень 3

Компания, продавая продукты, желает упаковывать их в пакеты. Информация о покупаемых продуктах находится в массиве строк data. Известно, что data[i][j] = 1, если i - ый покупатель покупает j - ый товар, иначе data[i][j] = 0. Два продукта могут быть упакованы в один пакет, если их либо покупают все покупатели, либо никто не покупает. Один пакет может содержать один товар, а каждый товар должен быть обязательно упакован в пакет. Необходимо найти наименьшее количество пакетов, необходимое для упаковки всех продуктов.

Класс: ProductBundling

Метод: int howManyBundles(vector<string> data)

Ограничения: data содержит от 1 до 50 элементов, каждый элемент data содержит одинаковое количество символов, от 1 до 50.

Вход. Массив data, содержащий информацию о покупаемых продуктах.

Выход. Наименьшее количество пакетов, необходимое для упаковки всех продуктов.

Пример входа

data

{"11100"}

{"1010", "1100"}

{"1100000000",

"1100000000",

"0011000000",

"0011000000",

"0000110000",

"0000110000",

"0000001100",

"0000001100",

"0000000011",

"0000000011"}

Пример выхода

2

4

5

РЕШЕНИЕ

обработка строк + структуры данных

Транспонируем матрицу data, после чего data[i][j] равно 1, если i - ый товар покупает j - ый покупатель. Товары i и j могут быть упакованы в один пакет тогда и только тогда, когда они одновременно продаются (или не продаются) всем покупателям, то есть если строки data[i] и data[j] одинаковы. Определяем и возвращаем количество разных строк в транспонированной матрице data.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <set>

using namespace std;

class ProductBundling

{

public:

int howManyBundles(vector<string> data)

{

set<string> s;

string temp;

int i, j;

for(i = 0; i < data[0].size(); i++)

{

for(temp = "", j = 0; j < data.size(); j++) temp = temp + data[j][i];

s.insert(temp);

}

return s.size();

}

};